COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input basic9
C00006 00003	\noindent {\:sS}
C00013 00004	\problem 1. Searching in 2D trees.
C00021 00005	\problem 2.  Shufflemerge.
C00030 00006	\problem 3. Oral exams.
C00034 00007	\problem 4. Distances.
C00037 00008	\hbox to size{AA Qual Answers\quad\leaders\hrule\hfill\quad June, 1979}
C00042 00009	\yskip{\bf 2.} a) Another parameter is needed in the merge procedure: If $x↓i=
C00048 00010	\yskip {\bf3.} a,b,c,d) The following solution allows for the case that several
C00056 00011	\yskip {\bf4.} For any two real matrices $A=(a↓{ij})$, $B=(b↓{ij})$, let
C00060 ENDMK
C⊗;
\input basic9
{\:c←ms25 \:s←sta200 }

% macros for use with Algol-like languages
{\:t←cmtt9 } % defines typewriter font
\def\Tb{10} % one unit of indentation (in points)
\def\Tbb{20} % two units of indentation (in points)
\def\\#1{\hbox{\it#1\/\hskip.5pt}} % italic type for identifiers
\def\.#1{\hbox{\:t#1}} % typewriter type for strings
\def\
{\hbox{\bf#1}} % boldface type for word delimiters
\def\_{\hskip.06em\vbox{\hrule width .4em}} % underline symbol within
	% identifiers (it's not present in the italic font)
\def\0{\hskip 0pt plus 10000pt\penalty0\hskip\Tbb pt plus-10000pt
	\hbox{\hskip-\Tbb pt}} % optional beginning of new line (a tricky macro)
\def\1{\advcount7 by \Tb \hangindent \count7pt} % indent one more unit
\def\2{\par \hangindent \count7pt \noindent
	\hbox{\hskip\count7pt \hskip-\Tbb pt}} % compulsory beginning of new line
\def\3{\advcount7 by-\Tb} % indent one less unit
\def\4#1{\hskip 0pt plus 10000pt\penalty#10
	\hskip 0pt plus-10000pt} % optional break with specified penalty
\def\5{\par\vskip 6pt plus 3pt minus 2pt\2} % compulsory line break after vskip
% To use these macros, start in vertical mode, then do this:
% {\ragged1000000 \jpar10000 \setcount7\Tbb\1 <your edited program> \par}

\def\xskip{\hskip 7pt plus 3pt minus 4pt}
\def\yskip{\vskip 3pt plus 2pt minus 1pt}
\def\subpart #1) {\noindent\hbox to 18pt{\hfill#1) }\!}
\def\problem #1. #2.{\noindent{\:q #1.\xskip #2.\par}}
\noindent {\:sS}

\vskip 1in
\hbox to size{A{\:dNALYSIS} {\:dOF} A{\:dLGORITHMS} Q{\:dUALIFYING}
E{\:dXAMINATION}\quad\leaders\hbox{\:cf}\hfill\quad
May, 1979}
\vskip .5in
\noindent This is an open book, open library, open computer exam; but you
should not ask any {\sl person} for help.

\vskip 6pt
\noindent Use a {\sl separate blue book} for each of the four problems. Write
your code number on each blue book.

\vskip 6pt
\noindent The exams are due one week from today, on June 1, 1979; turn them
in to Phyllis Winkler, Room 362, by 12 noon.

\vskip 12pt
\ctrline{\hbox par 300pt{{\sl Strategic considerations:}\xskip
Partial credit will be given for
incomplete answers, so show your work even if it wasn't a total success.
It is not expected that anybody will solve all parts of all the problems, so
do not worry if you are stuck on one part: don't get bogged down on a problem
to the extent that you won't have time to do others that are easier for you!
And please get plenty of sleep, even if you haven't completed the exam.}}

\vskip 12pt
\noindent Sign this sheet and turn it in with your blue books.\xskip
(It will be separated from the blue books while they are being graded, so your
anonymity will be preserved.)

\vskip 24pt \noindent
{\it I certify that I have neither received nor given unpermitted help
on this examination.}

\vskip 20pt
{\tabskip 0pt plus 100pt\halign to size{\ctr{#}\tabskip 0pt⊗\quad\ctr{#}\cr
\vrule height .5pt width 3in⊗$\#$ \vrule height .5pt depth 0pt width 1in\cr
(Signed)⊗(Code number)\cr}}

\vfill\eject
\problem 1. Searching in 2D trees.

\noindent Bentley's algorithm for inserting two-dimensional data points
$(x,y)$ into a 2D tree $T$ can be expressed as follows in pidgin PASCAL:

\yskip
{\ragged1000000 \jpar10000 \setcount7\Tbb\1 % Beginning BLAISE output:
\3\5\1\&{type} $\\{node}=\null$\1\2\&{record} \0$\\{x\_coord},\45\\{y\_coord}\mathrel:\\{real}$;
\2$\\{left\_son},\45\\{right\_son}\mathrel:{\up}\\{node}
$\2\&{end}$\null\3
$;
\3\2\1\&{var} $\\{T}={\up}\\{node}$;
\3\2\1\1\&{procedure} $\\{insert0}(\\{x},\45\\{y}\mathrel:\\{real};\42\,\mathop{\&{var}}
\\{p}
\mathrel:
{\up}
\\{node}
)
$;\40\ $\{\;$insertion on even levels$\;\}$
\3\2\&{begin} \0\1\&{if} $\\{p}=\&{nil}$ \&{then}
\0$\\{new\_leaf}(\\{x},\45\\{y},\45\\{p})$\3
\2\&{else} \0\1\&{if} $\\{x}<\\{p}{\up}.\\{x\_coord}$ \&{then}
\0$\\{insert1}(\\{x},\45\\{y},\45\\{p}{\up}.\\{left\_son})
$\3
\2\&{else} \0$\\{insert1}(\\{x},\45\\{y},\45\\{p}{\up}.\\{right\_son})
$
;
\2\&{end};
\3\2\1\1\&{procedure} $\\{insert1}(\\{x},\45\\{y}\mathrel:\\{real};\42\,\mathop{\&{var}}
\\{p}
\mathrel:
{\up}
\\{node}
)
$;\40\ $\{\;$insertion on odd levels$\;\}$
\3\2\&{begin} \0\1\&{if} $\\{p}=\&{nil}$ \&{then}
\0$\\{new\_leaf}(\\{x},\45\\{y},\45\\{p})$\3
\2\&{else} \0\1\&{if} $\\{y}<\\{p}{\up}.\\{y\_coord}$ \&{then}
\0$\\{insert0}(\\{x},\45\\{y},\45\\{p}{\up}.\\{left\_son})
$\3
\2\&{else} \0$\\{insert0}(\\{x},\45\\{y},\45\\{p}{\up}.\\{right\_son})
$
;
\2\&{end};
\3\2\1\1\&{procedure} $\\{new\_leaf}(\\{x},\45\\{y}\mathrel:\\{real};\42\,\mathop{\&{var}}
\\{p}
\mathrel:
{\up}
\\{node}
)
$;
\3\2\&{begin} \0$\\{new}(\\{p})$;
\2\1\&{with} $\\{p}$ \&{do}
\2\&{begin} \0$\\{x\_coord}\mathrel:=\\{x}$;
\0$\\{y\_coord}\mathrel:=\\{y}$;
\0$\\{left\_son}\mathrel:=\&{nil}$;
\0$\\{right\_son}\mathrel:=\&{nil}$;
\2\&{end}\3
;
\2\&{end};
\par} % end of BLAISE output
\yskip
\noindent We obtain a random 2D tree with $n$ nodes by setting \\T := \&{nil}
and then performing $\\{insert0}(x[i],y[i],T)$ for $1≤i≤n$, where the $x[i]$
and $y[i]$ are independent random real numbers, uniformly distributed between
0 and 1.

The following recursive procedures can be used to find the minimum $x$
coordinate of all keys in the tree:

\yskip
{\ragged1000000 \jpar10000 \setcount7\Tbb\1 % Beginning BLAISE output:
\3\2\1\1\&{function} $\\{min0}(\\{p}\mathrel:{\up}\\{node})\mathrel:\\{real}
$;\40\ $\{\;$minimum on even levels$\;\}$
\3\2\&{begin} \0\1\&{if} $\\{p}=\&{nil}$ \&{then}
\0$\\{min0}\mathrel:=1.0$\3
\2\&{else} \0\1\&{if} $\\{p}{\up}.\\{left\_son}=\&{nil}$ \&{then}
\0$\\{min0}\mathrel:=\\{p}{\up}.\\{x\_coord}$\3
\2\&{else} \0$\\{min0}\mathrel:=\\{min1}(\\{p}{\up}.\\{left\_son})
$
;
\2\&{end};
\3\2\1\1\&{function} $\\{min1}(\\{p}\mathrel:{\up}\\{node})\mathrel:\\{real}
$;\40\ $\{\;$minimum on odd levels, \\p not nil$\;\}$
\3\2\1\&{var} $\\{x\_left},\45\\{x\_right},\45\\{x}\mathrel:\\{real}
$;
\3\2\&{begin} \0$\\{x\_left}\mathrel:=\\{min0}(\\{p}{\up}.\\{left\_son})
$;
\0$\\{x\_right}\mathrel:=\\{min0}(\\{p}{\up}.\\{right\_son})
$;
\2\1\&{if} $\\{x\_left}<\\{x\_right}$ \&{then}
\0$\\{x}\mathrel:=\\{x\_left}$\3
\2\&{else} \0$\\{x}\mathrel:=\\{x\_right}$
;
\2\1\&{if} $\\{x}<\\{p}{\up}.\\{x\_coord}$ \&{then}
\0$\\{min1}\mathrel:=\\{x}$\3
\ \&{else} \0$\\{min1}\mathrel:=\\{p}{\up}.\\{x\_coord}$
;
\2\&{end};
\par} % end of BLAISE output
\penalty-100 % good place to break the page
\yskip
The purpose of this problem is to analyze the average running time of such an
algorithm, when it is applied to random 2D trees. If $T$ points
to the root of a random 2D tree with $n$ nodes, and if we perform the function
call $\\{min0}(T)$, let $A↓n$ be the average number of times the function
\\{min0} is invoked. Find a ``closed form'' expression for $A↓n$, and determine
its asymptotic behavior as $n→∞$ to an accuracy of $O(n↑{-1})$.

{\sl Notes:}\xskip
The following values for small $n$ should be helpful to make sure you
understand the problem.
$$\baselineskip 14pt
\vbox{\halign{$\hfill#=\null$⊗ \ctr{#}⊗\qquad\ctr{#}⊗\qquad\ctr{#}⊗\qquad
\ctr{#}\cr
n⊗0⊗1⊗2⊗3\cr
A↓n⊗1⊗1⊗2⊗7/3\cr}}$$
The formula for $A↓n$ involves the binomial coefficient ${α\choose n}(-1)↑n$
for a certain real number $α$ between $-1$ and $-2$. If you don't figure out
the correct formula for $A↓n$, you can get partial credit on the asymptotic
part of this question {\sl if and only if\/} you explain how to get the
asymptotic behavior of ${α\choose n}(-1)↑n$ for fixed $α$ between $-1$ and $-2$.

\vfill\eject
\problem 2.  Shufflemerge.
\noindent (This problem is based on a interesting new sorting scheme that is
similar to an algorithm developed recently by John A. Ellis.)\xskip
We shall make use of the following two types of permutations on an array $x$:

\yskip\hangindent 36pt
Procedure $\\{Shuffle}(s,m)$ replaces $(x↓s,x↓{s+1},\ldotss,x↓{s+m-1},x↓{s+m},
x↓{s+m+1},\ldotss,x↓{s+2m-1})$ respectively by $(x↓{s+m},x↓s,x↓{s+m+1},x↓{s+1},
\ldotss,x↓{s+2m-1},x↓{s+m-1})$.

\yskip\hangindent 36pt
Procedure $\\{Unshuffle}(s,m)$ does the inverse permutation.

\yskip
\noindent For example, if $(x↓1,\ldotss,x↓{11})=(A,B,C,D,E,F,G,H,I,J,K)$, the
result of $\\{Shuffle}(3,4)$ would be to replace the array by
$(A,B,G,C,H,D,I,E,J,F,K)$, and a subsequent $\\{Unshuffle}(2,3)$ would change
this to $(A,G,H,I,B,C,D,E,J,F,K)$. The cost of $\\{Shuffle}(s,m)$ and of
$\\{Unshuffle}(s,m)$ is 2m.

\yskip
In terms of these primitive operations, we can define a recursive procedure
$\\{Merge}(s,m,n)$ for {\sl merging in place}. Namely, $\\{Merge}(s,m,n)$ is
applied to an array such that
$$x↓s≤x↓{s+1}≤\cdots≤x↓{s+m-1}\qquad\hbox{and}\qquad x↓{s+m}≤x↓{s+m+1}≤\cdots
≤x↓{s+m+n-1}$$
and it permutes these $m+n$ elements so that
$$x↓s≤x↓{s+1}≤\cdots≤x↓{s+m+n-1}.$$
Here is a sketch of $\\{Merge}(s,m,n)$:

\vskip 10pt
{\ragged1000000 \jpar10000 \setcount7\Tbb\1 % Beginning BLAISE output:
\5\1\&{if} $\\{m}>\\{n}$ \&{then}
\2\&{begin} Do the same as when $m<n$ with the r\A oles of $m$ and $n$ reversed,\40
``reflecting'' all the operations with respect to left and right;
\2\&{end}\3
\2\&{else} \0\1\&{if} $\\{m}>0$ \&{then}
\2\&{begin} \0$\\{Shuffle}(\\{s}+1,\45\\{m}-1)$;
\0$\\{j}←\\{s}+2\times m-1$;
\0$\\{r}←\\{s}+\\{m}+\\{n}$;
\2\1\&{while} $\\{j}>\\{s}$ \&{do}
\2\&{begin} \0\&{comment} Now we have
$$\baselineskip14pt\eqalign{
x↓{j-1}⊗≤x↓r\quad\hbox{or}\quad r=s+m+n,\cr
\hbox{and}\quad x↓i⊗≤x↓{i+2}\quad\hbox{for $s≤i≤j-2$,}\cr
\hbox{and}\quad x↓i⊗≤x↓{i+1}\quad\hbox{for $j≤i≤s+m+n-2$;}\cr}$$
\2\1\&{if} $\\{x}↓{\\{j}-1}≤\\{x}↓{j}$ \&{then}
\2\&{begin} \0$\\{r}←\\{j}$;
\0$\\{j}←\\{j}-1$;
\2\&{end}\3
\2\&{else} \1\&{begin} \0$\\{k}←\\{j}-3$;
\2\1\&{while} $\\{k}≥\\{s}\mathbin{\&{and}}\\{x}↓{k}>\\{x}↓{j}
$ \&{do}
\0$\\{k}←\\{k}-2$\3;
\2$\\{p}←(\\{j}-\\{k}-1)/2$;
\0$\\{Unshuffle}(\\{k}+2,\45\\{p})$;
\0\&{comment} Now $x↓{k+2}≤x↓{k+3}≤\cdots≤x↓j$;
\2$\\{Merge}(\\{j}-\\{p}+1,\45\\{p},\45\\{r}-\\{j}-1)$;
\0$\\{r}←\\{j}-\\{p}$;
\0$\\{j}←\\{r}-\\{p}$;
\2\&{end}\3
;
\2\&{end}\3
;
\2\&{end}\3
\par} % end of BLAISE output
\yskip
\subpart a) Explain what changes should be made to this program to guarantee
that the merging will be stable.\xskip(In other words, if the \\{Shuffle} and
\\{Unshuffle} procedures were to act on an auxiliary array $y$
just as they do on $x$, and if $y↓i=i$ initially for all $i$, then after
the merging takes place we should have $y↓i<y↓j$ whenever $x↓i=x↓j$ and $i<j$.)

\yskip
\subpart b) Suppose $s=1$ and $1≤m≤n$. Let $j↓1>j↓2>\cdots>j↓t$ be the values of
$j$ occurring when the test ``$j>s$'' is made during the execution of
$\\{Merge}(1,m,n)$, considering only the top level of the recursion (not the
recursive calls). For example, when $m=10$, $n=20$, and
$x↓1\ldotsm x↓{30}=1\,2\,3\,5\,7\,18\,21\,23\,28\,30\,4\,6\,8\,9\,10\,11\,12\,13
\,14\,15\,16\,17\,19\,20\,22\,24\,25\,26\,27\,29$
we have $j↓1, \ldotss, j↓t=20, 10, 9, 5, 1$.

Show that the following quantities, which govern the running time, can be
expressed in terms of $j↓1$, $\ldotss$, $j↓t$, $m$, and $n$:

\yskip\hangindent 36pt
How often is the comparison ``$x↓{j-1}≤x↓j$'' made on the top level?

\yskip\hangindent 36pt
How often is the comparison ``$x↓k>x↓j$'' made on the top level?

\yskip\hangindent 36pt
What are the costs of the \\{Shuffle} and \\{Unshuffle} operations
performed on the top level?

\yskip\hangindent 36pt
What are the sizes $(m↓i,n↓i)$ of the subfiles to be merged by recursive calls
of \\{Merge} from the top level?

\yskip
\subpart c) Let the elements $x↓1$, $\ldotss$, $x↓{m+n}$ be distinct, and assume
that all $m+n\choose n$ arrangements of these elements such that $x↓1<\cdots<x↓m$
and $x↓{m+1}<\cdots<x↓{m+n}$ are equally likely; such input leads to so-called
{\sl random} $(m,n)$ merges. Using the notation of part (b), what is the
probability that a given set of values $j↓1>\cdots>j↓t$ will occur in a random
$(m,n)$ merge?\xskip Are the recursive calls to \\{Merge} made by the top
level of a random $(m,n)$ merge always random $(m↓i,n↓i)$ merges?\xskip
[If so, the distribution of $j↓1$, $\ldotss$, $j↓t$ will suffice to determine
the average running time, at least in principle. However, determination of
the average running time is beyond the scope of this exam.]

\yskip
\subpart d) The \\{Merge} procedure is intended to merge in place. However, prove
that if it is implemented as stated, it might need $\Omega(m+n)$ auxiliary
storage locations for stack space. Show how to modify the algorithm so that
the recursion depth will be only $O\biglp\log(2\min(m,n))\bigrp$ when $mn≠0$.

\yskip
\subpart e) Let $T(m,n)$ be the number of comparisons made when \\{Merge} merges
$m$ elements with $n$. By definition of the algorithm we have $T(0,n)=0$ and
$T(n,m)=T(m,n)$. Prove or disprove that $T(m,n)=O\biglp(m+n)\log(2\min(m,n))\bigrp$
when $mn≠0$.

\vfill\eject
\problem 3. Oral exams.

Let $P$ be a colection of professors, $S$ a collection of students, and $E$
a collection of professor-student pairs. Each pair $(p,s)$ represents an
oral exam that student $s$ must take from professor $p$. The schedule must be
arranged so that no professor gives two exams simultaneously and no student
takes two exams simultaneously. Each exam lasts three
hours, and we wish to schedule them so that the number of examination
periods is minimized.

Example: $P=\{\hbox{Don},\hbox{Bob},\hbox{Frances}\}$, $S=\{\hbox{Lyle},\hbox{Greg}\}$,

$E=\{(\hbox{Don},\hbox{Lyle})$,
$(\hbox{Don},\hbox{Greg})$,
$(\hbox{Bob},\hbox{Lyle})$,
$(\hbox{Frances},\hbox{Lyle})$,
$(\hbox{Frances},\hbox{Greg})\}$.

\noindent A minimum schedule is:
$$\vbox{\halign{\ctr{#}⊗\quad\ctr{#}⊗\quad\ctr{#}\cr
{\sl Period}⊗{\sl Room 1}⊗{\sl Room 2}\cr
\noalign{\vskip 3pt}
1⊗(Don, Lyle)⊗(Frances, Greg)\cr
2⊗(Don, Greg)⊗(Bob, Lyle)\cr
3⊗(Frances, Lyle)\cr}}$$

\yskip\subpart a) Prove that the minimum number of periods necessary is exactly the
maximum of $d↓p$ and $d↓s$, where $d↓p$ is the maximum number of exams to be
given by any professor and $d↓s$ is the maximum number of exams to be taken by
any student.

\yskip\subpart b) Give a polynomial-time algorithm that obtains a minimum-time schedule.

\yskip\subpart c) Suppose the exams are to be scheduled into rooms such that no two
exams take place in the same room at the same time. Prove that the exams can be
scheduled into $\lceil m/d\rceil$ rooms, where $m$ is the total number of exams
and $d=\max(d↓p,d↓s)$ is the number of exam periods.

\yskip\subpart d) Give a polynomial-time algorithm to schedule the exams into $d$
periods and $\lceil m/d\rceil$ rooms.

\yskip\subpart e) Suppose each professor wants to hold all his exams in the same room.
Show that in this case it is not always possible to meet both the $\lceil m/d\rceil
$-room and $d$-period constraints.

\yskip\subpart f) Show that it is NP-complete to determine whether a given set
of exams can be scheduled in $r$ rooms and $t$ periods, given $r$ and $t$, if
professors refuse to change rooms.

\yskip\subpart g) [For extra credit only.]\xskip Is the above problem still
NP-complete when room-changing is allowed?

\vfill\eject
\problem 4. Distances.

Let $E↑k$ be the space of all $k$-tuples of real numbers. In the $L↓∞$-metric,
the distance $d(\b u,\b v)$ between any two points $\b u=(u↓1,\ldotss,u↓k)$ and
$\b v=(v↓1,\ldotss,v↓k)$ in $E↑k$ is defined to be $\max\leftset|u↓i-v↓i|
\≥\left|\≥1≤i≤k\rightset\right.$. Given $n$ points ${\b x}↓1$, ${\b x}↓2$,
$\ldotss$, ${\b x}↓n$ in $E↑k$, their $n\times n$ {\sl all-distance matrix} $M=\biglp
d(x↓i,x↓j)\bigrp$ can obviously be computed in $O(kn↑2)$ time. We would like
to show that the complexity can be lowered when $k$ is large. Specifically,
prove that $M$ can be computed in $o(n↑3)$ time when $k=n$, where `time' refers
to the number of real arithmetic operations and tests needed on a random-access
computer.

{\sl Hints:}\xskip You may use the following result due to Fredman. Let
$G$ be a directed graph on $n$ vertices $\{1,2,\ldotss,n\}$ with a nonnegative
weight assigned to each edge. For every pair $i≠j$, let $a↓{ij}(G)$ be the
minimum weighted length of any path from vertex $i$ to vertex $j$. It is
known that, given $G$, the $n\times n$ matrix $\biglp a↓{ij}(G)\bigrp$ can
be computed in $O\biglp n↑3(\log\log n\,/\log n)↑{1/3}\bigrp$ time.\xskip
[Fredman's paper appeared in {\sl SIAM J. Computing \bf5} (1976), 83-89; but
you need not read the paper to solve this problem!]\xskip You may also find the
material in Aho, Hopcroft, & Ullman $\section\section$5.6-5.10 useful. Think
about working with $2n\times2n$ matrices in order to derive an $n\times n$ result.

\vfill\eject
\hbox to size{AA Qual Answers\quad\leaders\hrule\hfill\quad June, 1979}
\vskip 10pt
{\bf1.} Nodes at even (resp. odd) levels of a subtree of size $m$ have
probability $1/m$ of having the $k$th smallest $x$ coordinate (resp. $y$
coordinate), for $1≤k≤m$. Thus we find $A↓0=1$ and
$$nA↓n=\sum↓{1≤k≤n}(1+B↓{k-1})\qquad\hbox{for all $n≥0$,}$$
where $B↓m$ is the number of times \\{min0} is invoked if we call $\\{min1}(p)$
when $p$ points to a random subtree of size $m$. We have $B↓0=0$ and
$$nB↓n=\sum↓{1≤k≤n}(A↓{k-1}+A↓{n-k})=2\sum↓{1≤k≤n}A↓{k-1}\qquad\hbox{for all
$n≥0$.}$$
Let $A(z)=\sum↓{n≥0}A↓nz↑n$ and $B(z)=\sum↓{n≥0}B↓nz↑n$ be the corresponding
generating functions. Then we find
$$\baselineskip14pt\eqalign{(1-z)A↑\prime(z)⊗=1/(1-z)+B(z),\cr
(1-z)B↑\prime(z)⊗=2A(z).\cr}$$
Let $\Phi$ be the linear operator $\Phi f(z)=(1-z)f↑\prime(z)$. Then
$\Phi(1-z)↑a=-a(1-z)↑a$, and we have the differential equation $\Phi↑2 A(z)=
\Phi(1-z)↑{-1}+\Phi B(z) = (1-z)↑{-1}+2A(z)$, i.e.,
$$(\Phi-\sqrt2)(\Phi+\sqrt2)A(z) = (1-z)↑{-1}.$$
The general solution to $(\Phi+a)f(z)=(1-z)↑b$ is $C(1-z)↑a+(a-b)↑{-1}(1-z)↑b$,
when $a≠b$, hence
$$A(z)=C↓1(1-z)↑{\sqrt2}+C↓2(1-z)↑{-\sqrt2}-{1\over 1-z}$$
for some $C↓1$ and $C↓2$. We can determine the constants by looking at $A↓0$ and
$A↓1$:
$$\baselineskip14pt\vbox{\halign{$\hfill#\null$⊗$\hfill#\null$⊗$\hfill#$\cr
1=A↓0=⊗C↓1+⊗C↓2-1,\cr
1=A↓1=⊗-\sqrt2 C↓1+⊗\sqrt2 C↓2-1.\cr}}$$
Thus $C↓1=1-1/\sqrt2$, $C↓2=1+1/\sqrt2$, and
$$A↓n=\bigglp1-{1\over\sqrt2}\biggrp{\sqrt2\,\choose n}(-1)↑n+
\bigglp1+{1\over\sqrt2}\biggrp{-\sqrt2\,\choose n}(-1)↑n-1.$$

To get the asymptotic value, we note that
$${\sqrt2\,\choose n}(-1)↑n={\sqrt2(\sqrt2-1)(2-\sqrt2)\ldotsm(n-1-\sqrt2)\over
n!}={\sqrt2(\sqrt2-1)\,\Gamma(n-\sqrt2)\over\Gamma(2-\sqrt2)\,\Gamma(n+1)}$$
and it will follow from our argument below that this is $O(n↑{-1-\sqrt2})$ so
we can ignore it. The main contribution is from
$${-\sqrt2\,\choose n}(-1)↑n={\sqrt2(\sqrt2+1)\ldotsm(\sqrt2+n-1)\over n!}
={\Gamma(n+\sqrt2)\over\Gamma(\sqrt2)\,\Gamma(n+1)}.$$
We have $\ln\Gamma(x)=x\ln x - x - {1\over2}\ln x+\ln\sqrt{2π}+{1\over 12x}+
O(x↑{-3})=\ln\Gamma(x+1)-\ln x$, and $\ln(n+\sqrt2)=\ln n+\sqrt2/n-1/n↑2+O(n↑{-3})$;
so $\ln\Gamma(n+\sqrt2)=(n+\sqrt2)\ln n+\sqrt2+2/n-/n+O(n↑{-2})-n-\sqrt2
-{1\over2}\ln n-\sqrt2/(2n)+\ln\sqrt{2π}+1/(12n)$ and $\ln\Gamma(n+1)=n\ln n
-n+{1\over2}\ln n+\ln\sqrt{2π}+1/(12n)+O(n↑{-3})$. It follows that
$$\baselineskip16pt\lineskip4pt\eqalign{{-\sqrt2\,\choose n}(-1)↑n
⊗={1\over\Gamma(\sqrt2)}\exp\bigglp\sqrt2\ln n-\ln n+\biglp1-{1\over\sqrt2\,}\bigrp
n↑{-1}+O(n↑{-2})\biggrp\cr
⊗={1\over\Gamma(\sqrt2)}n↑{\sqrt2-1}\,\bigglp 1+\biglp 1-{1\over\sqrt2\,}\bigrp
n↑{-1}+O(n↑{-2})\biggrp,\cr
A↓n⊗={1\over\Gamma(\sqrt2)}\bigglp\biglp 1+{1\over\sqrt2\,}\bigrp n↑{\sqrt2-1}
{1\over2}n↑{\sqrt2-2}\biggrp-1+O(n↑{\sqrt2-3}).\cr}$$
Note that $A↓n$ grows more slowly than $\sqrt n$, although we would obtain a
function of order $\sqrt n$ on a perfectly balanced tree.
\yskip{\bf 2.} a) Another parameter is needed in the merge procedure: If $x↓i=
x↓j$ where $i<s+m$ and $j≥s+m$, we want to regard $x↓i<x↓j$ if $b=0$, but
$x↓i>x↓j$ if $b=1$. At the top level call we have $b=0$. During the execution
of the procedure, $b=0$ will mean that $x↓j$ belongs to the subfile whose
keys are ``larger.'' Thus, \\{Stablemerge}$(s,m,n,b)$ is like \\{Merge}$(s,m,n)$
but with the following changes:
$$\baselineskip14pt\eqalign{
x↓{j-1}≤x↓j\quad\char'771\quad⊗x↓{j-1}<x↓j\ \&{or}\ (x↓{j-1}=x↓j\ \&{and}\ b=0)\cr
x↓k>x↓j\quad\char'771\quad⊗x↓k>x↓j\ \&{or}\ (x↓k=x↓j\ \&{and}\ b=1)\cr
j←j-1\quad\char'771\quad⊗j←j-1;\ b←1-b\cr
\\{Merge}(j-p+1,p,r-j-1)\quad\char'771\quad⊗\\{Stablemerge}(j-p+1,p,r-j-1,b)\cr}$$

\yskip
\subpart b) Note that either $j↓{i+1}=j↓i-1$ or $j↓i-j↓{i+1}$ is even. Let $p↓i=
\lfloor(j↓i-j↓{i+1})/2\rfloor$ for $i≥1$, and $p↓0=n-m+1$. For $1≤i<t$ the $i$th
iteration does the following:
$$\vbox{\halign{#\hfill\cr
$x↓{j-1}≤x↓j$ tested once;\cr
$x↓k>x↓j$ tested $p↓i$ times (except $p↓i-1$ when $i=t-1$ and $p↓i≠0$);\cr
\\{Unshuffle} of cost $2p↓i$;\cr
Merge of $p↓i$ elements with $p↓{i-1}-1$ elements (or with 0 if $p↓{i-1}=0$).\cr}}$$
Thus, $x↓{j-1}≤x↓j$ is tested $t-1$ times, $x↓k>x↓j$ is tested $\sum p↓i$ times
(or possibly one less); there is one \\{Shuffle} of cost $2m-2$; the \\{Unshuffle}s
cost $2\sum p↓i$; and the merges are of sizes $(m↓i,n↓i)=(p↓i,p↓{i-1}-1)$.\xskip
$\biglp$Note that $\sum↓{1≤i<t}p↓i=m-\lceil z/2\rceil$ when exactly
$z$ of the $p↓i$ are zero.$\bigrp$

\yskip
\subpart c) Consider the array after the initial \\{Shuffle} operation; all
permutations such that $x↓1<x↓3<\cdots<x↓{2m-1}$ and $x↓2<x↓4<\cdots<x↓{2m}<x↓{2m+1}
<\cdots<x↓{m+n}$ are equally likely. The permutations leading to a particular set
of indices $j↓1>\cdots>j↓t$ are such that the rank of each $x↓{j↓i}$ is known:
If $j↓{i+1}=j↓i-1$ we have $x↓{j↓{i+1}}<x↓{j↓i}$ and otherwise we have
$x↓{j↓{i+1}-1}<x↓{j↓i}<x↓{j↓{i+1}+1}$. For example, when $m=10$ and $n=20$,
we get $j↓1\ldotsm j↓t = 20\,10\,9\,5\,1$ if and only if $x↓9<x↓{20}<x↓{11}$,
$x↓9<x↓{10}$, $x↓4<x↓9<x↓6$, $x↓5<x↓2$; the resulting partial order is
$$\ctrline{$\dispstyle x↓1<x↓3<x↓5<{x↓2<x↓4\atop x↓7}<x↓9<x↓6<x↓8<\cdots<
x↓{20}<{x↓{11}<x↓{13}<x↓{15}<x↓{17}<x↓{19}\atop x↓{21}<x↓{22}<x↓{23}<\cdots<x↓{30}}.
$}$$
In general the number of permutations satisfying the partial order is $\prod
↓{1≤i<t}{m↓i+n↓i\choose m↓i}$, hence the randomness of subfiles is inherited.

\yskip
\subpart d) When $m=1$ and $x↓1=\max(x↓1,\ldotss,x↓{1+n})$ the recursion reaches
depth $n$. The first recursive call on \\{Merge} has $m↓1=p↓1$ and $n↓1=n-m$;
this is the only one in which $\min(m↓i,n↓i)>m/2$. For if $1<i<t$ we have
$m↓i+n↓i<p↓i+p↓{i-1}≤(j↓{i-1}-j↓{i+1})/2≤(j↓1-j↓t)/2≤m$, so either $m↓i$ or
$n↓i$ must be $<m/2$. The trick is therefore not to do the first merge right
away; we save the values of $j↓1-p↓1+1$, $p↓i$, and $p↓0-1$. Then after all the
other recursive merges have been done, we reset the values of $(s,m,n)$ and
return to the beginning of the procedure instead of recursing.

\yskip
\subpart e) Let $m≤n$. We have $T(m,n)≤c↓1m+\sum↓{1≤i<t}T(m↓i,n↓i)$ for some
$c↓1$, and for $i>1$ we proved in (d) that $\min(m↓i,n↓i)<{1\over2}\min(m,n)$.
Furthermore $m↓1≤m$, $n↓1≤n-m$, and $\sum↓{1<i<t}(m↓i+n↓i)≤p↓1+2p↓2+\cdots+
2p↓{t-2}+p↓{t-1}≤2(p↓1+\cdots+p↓{t-1}-m↓1≤2m-m↓1$. Hence if we assume that
$T(m↓i,n↓i)≤c↓2(m↓i+n↓i)\lg 2\min(m↓i,n↓i)$ when $m↓in↓i≠0$ we have
$$T(m,n)≤c↓1m+c↓2(m↓1+n-m)\lg 2m+c↓2(2m-m↓1)\lg m.$$
This is $≤c↓2(m+n)\lg 2m$ if we choose $c↓2≥c↓1$.
\yskip {\bf3.} a,b,c,d) The following solution allows for the case that several
exams might involve the same professor-student pair.

If $m$ is not a multiple of $d$, there must be some $p$ and some $s$ that do not
have $d$ exams to meet; we can add $(p,s)$ to the set $E$ and increase $m$ by 1.\xskip
(Afterwards this additional exam can be dropped from the schedule.)\xskip
Thus we can assume that $m$ is a multiple of $d$, and the schedule must fill
$r=m/d$ rooms during each of $d$ periods.

If there are more students than professors, we can add professors who are
assigned to no exams; similarly if there are excess professors, we can add idle
students. Thus we can assume that the number of students equals the number of
professors, say $n$. Since $nd≥m=rd$ we have $n≥r$.

Now we add $n-r$ dummy students and ask for additional exams between dummy
students and professors in such a way that every dummy student is in $d$ exams
and every non-dummy professor is in $d$ exams. We also add $n-r$ dummy professors and
ask for additional exams between dummy professors and students in such a way that
every dummy professor is in $d$ exams and every non-dummy student is in $d$ exams. The
resulting system has $2n-r$ professors, $2n-r$ students, and $rd+(n-r)d+(n-r)d=
(2n-r)d$ exams. If we can schedule this system into $d$ exam periods, every period will
involve $2n-r$ exams, with all $2n-r$ professors and all $2n-r$ students taking
part. Furthermore $n-r$ of these exams will involve dummy students meeting real
professors, and $n-r$ will have dummy professors meeting real students, so we
need not assign rooms to them; exactly $r$ rooms are needed for the real profs
and the real studs.

In other words it suffices to solve the problem for the case that every professor
and every student takes part in exactly $d$ exams, possibly with multiple
exams between the same pair. And all we have to do for that case is show how
to make a schedule for the first period, since this reduces $d$ by 1.

But the first period schedule is simply a bipartite matching, and such matchings
are well known to be efficiently findable in the equal-degree case. For completeness,
an algorithm is sketched here: Suppose we have scheduled $l-1$ exams for the
first period, where $1≤l≤n$, and we wish to schedule the $l$th exam. Consider the
following directed graph: A student $s$ is called ``free'' if he is not among
the $l-1$ students already scheduled. Otherwise suppose $s$
is already scheduled with professor $p$; we write $s→s↑\prime$ for all students
$s↑\prime$ that $p$ must examine. This digraph is readily constructed from the
known information. Now let $p$ be a free professor, and let $s$ be any of
$p$'s examinees. We claim that there exists a directed path $s\mathrel{{→}{*}}t$
where $t$ is a free student. For if not, let there be $q$ students reachable
from $s$, including $s$ itself, and consider the $q$ professors they are
scheduled with. These $q$ professors account for $qd$ exams (counting multiplicities),
and the exam between $p$ and $s$ makes $qd+1$. But this contradicts the fact that
the $q$ students participate in only $qd$ exams (counting multiplicities).\xskip
$q$ $E$ $d$.\xskip From the path $s=s↓0→s↓1→\cdots→s↓u=t$, which can be found by
depth-first search, we now can fashion a new schedule: If $p↓i$ is assigned to
$s↓i$ for $0≤i<u$, let instead $p↓i$ be assigned to $s↓{i+1}$, and schedule $p$
with student $s=s↓0$.

\yskip\subpart e) For example, if $d=3$ and there are four professors participating
in 3, 2, 2, 2 exams, it is impossible to fit them into 3 rooms and 3 periods.

\yskip\subpart f) It is NP-complete even if each exam involves a different student.
For the problem is clearly in NP. Conversely we can reduce 3-PARTITION to it
[see Garey & Johnson, p.96]: The set $A$ is the set of $3m$ professors, the
sizes $s(a)$ are the number of exams for professor $a$, and we take $r=m$, $t=B$.

\yskip\subpart g) Not if $\hbox{P}≠\hbox{NP}$, since there is a polynomial
algorithm to find a schedule in $r$ rooms and $t$ periods whenever $t≥d$ and
$rt≥m$. First, find any solution using $d$ periods and any number of rooms.
If this solution requires $r↓1>r$ rooms during time period 1 and $r↓2<r$ rooms
during time period 2, there is a way to modify it so that $r↓1-1$ and $r↓2+1$
rooms are needed instead, by rearranging exams.\xskip(Superposing the
schedules for periods 1 and 2 leads to the existence of a maximal path containing
one more exam from period 1 than from period 2; switch the exams on such a path.)
\yskip {\bf4.} For any two real matrices $A=(a↓{ij})$, $B=(b↓{ij})$, let
$A∧B$ denote the matrix $(c↓{ij})$ where $c↓{ij}=\min\{a↓{ij},b↓{ij}\}$,
and let $A\otimes B$ denote the ``min-plus product'' matrix 
$(c↑\prime↓{ij})$ where $c↑\prime↓{ij}=
\min↓k\{a↓{ik}+b↓{kj}\}$. Use $A*$ to denote the reflexive transitive
closure under $∧$ and $+$, that is, $A*=I∧A∧A↑2∧\cdots∧A↑n$ where $A↑j=A↑{j-1}
\otimes A$ and $I$ is the identity matrix with respect to $∧$. Two well known
facts are:

\yskip\hangindent 18pt\noindent
\hbox to 18pt{\hfill i) }The computation of the shortest distances for any
directed graph $G$ with the nonnegative weight matrix $A=(a↓{ij})$ is the
same as computing $A*$;

\yskip\hangindent 18pt\noindent
\hbox to 18pt{\hfill ii) }The complexity of computing $A*$ is asymptotically
the same as computing $A \otimes B$.

\yskip\noindent
(The proof of (ii) in AHU works for nonnegative $A$ and $B$; by adding a
suitable constant to the elements, we can reduce the general case of computing
$A\otimes B$ to the case where $A$ and $B$ are nonnegative.)\xskip
As a result of these facts and Fredman's algorithm mentioned in the hint,
the computation of $A\otimes B$ can be done in $O\biglp n↑3(\log\log n/\!\log n)
↑{1/3}\bigrp$ time.

We now turn to our problem, which we shall generalize as follows: Given $2n$
points $\b x↓1$, $\ldotss$, $\b x↓n$, $\b y↓1$, $\ldotss$, $\b y↓n$ in $E↑n$,
let us compute the $n\times n$ matrix $M=\biglp d(\b x↓i,\b y↓j)\bigrp$.
Clearly
$$\baselineskip14pt\eqalignno{-d(\b x↓i,\b y↓j)⊗=\min↓{1≤k≤n}
\{-|x↓{ik}-y↓{jk}|\}\cr
⊗=\min↓{1≤k≤n}\{x↓{ik}-y↓{jk},-x↓{ik}+y↓{jk}\}.⊗(1)\cr}$$
Define $2n$ points $\b z↓i$, $\b w↓i$ in $E↑{2n}$ for $1≤i≤n$ by the formulas
$$\baselineskip14pt\eqalign{
\b z↓i⊗=(\b x↓i,-\b x↓i)=(x↓{i1},\ldotss,x↓{in},-x↓{i1},\ldotss,-x↓{in}),\cr
\b w↓i⊗=(-\b y↓i,\b y↓i)=(-y↓{i1},\ldotss,-y↓{in},y↓{i1},\ldotss,y↓{in}).\cr}$$
Consider the $2n\times 2n$ matrix $N$ having rows $\b z↓1$, $\ldotss$, $\b z↓n$,
$\b w↓1$, $\ldotss$, $\b w↓n$ from top to bottom. It is easy to verify, using
(1), that
$$N\otimes N↑T=\left(\,\vcenter{\halign{\ctr{$\dispstyle#$}⊗\quad
\ctr{$\dispstyle#$}\cr
\ast⊗-M\cr -M↑T⊗\ast\cr}}\,\right).$$
Thus, the computation of $M$ can be reduced to the computation of $N↑T\otimes N$,
which can be done in $O\biglp n↑3(\log\log n/\!\log n)↑{1/3}\bigrp$ time.

\vfill\end